#include <iostream>
#include <cassert>
#include <algorithm>
#include "SortTestHelper.h"

using namespace std;
template <typename Item>
class IndexMaxHeap{
private:
    Item *data;
    int* indexes;
    int* reverse;
    int count;
    int capacity;
    void shiftUp(int k) {
//        int  e=indexes[k];
        while (k > 1 && data[indexes[k/2]] <data[indexes[k]]) {
            swap(indexes[k/2],indexes[k]);
//            indexes[k]=indexes[k/2];
            reverse[indexes[k/2]]=k/2;
            reverse[indexes[k]]=k;
            k/=2;
        }
//        indexes[k]=e;
    }
    void shiftDown(int k) {
        while (2*k<=count){
            int j=2*k;
            if(j+1<=count && data[indexes[j+1]]>data[indexes[j]])
                j+=1;
            if(data[indexes[k]]>=data[indexes[j]])
                break;
            swap(indexes[k],indexes[j]);
            reverse[indexes[k]]=k;
            reverse[indexes[j]]=j;
            k=j;
        }
    }
public:
    IndexMaxHeap(int capacity){
        data=new Item[capacity+1];
        indexes=new int[capacity+1];
        reverse=new int[capacity+1];
        count=0;
        this->capacity=capacity;
    }

    ~IndexMaxHeap(){
        delete[] data;
        delete[] indexes;
    }
    int size(){
        return count;
    }
    bool isEmpty(){
        return count==0;
    }

    void insert(int i,Item item) {
        assert(count+1<=capacity);
        assert(i+1>=1&& i+1<=capacity);
        i+=1;
        data[i]=item;
        indexes[count+1]=i;
        reverse[i]=count+1;
        count++;
        shiftUp(count);
    }

    Item  extractMax(){
        assert(count>0);

        Item ret=data[indexes[1]];
        swap(indexes[1],indexes[count]);
        reverse[indexes[1]]=1;
        reverse[indexes[count]]=0;
        count--;
        shiftDown(1);
        return ret;
    }
    Item extractMaxIndex(){
        assert(count>0);
        int ret=indexes[1]-1;
        swap(indexes[1],indexes[count]);
        reverse[indexes[1]]=1;
        reverse[indexes[count]]=0;
        count--;
        shiftDown(1);
        return ret;
    }
    Item getMax(){
        assert(count>0);
        return data[indexes[1]];
    }
    int getMaxIndex(){
        assert(count>0);
        return indexes[1]-1;
    }
    bool contain(int i){
        assert(i+1>=1&&i+1<=count);
        return reverse[i+1]!=0;
    }
    Item getItem(int i){
        assert(contain(i));
        return data[indexes[i+1]];
    }

    void change(int i, Item newItem) {
        assert(contain(i));
        i+=1;
        data[i]=newItem;
        shiftDown(reverse[i]);
        shiftUp(reverse[i]);
    }
    bool testIndexes(){

        int *copyIndexes = new int[count+1];

        for( int i = 0 ; i <= count ; i ++ )
            copyIndexes[i] = indexes[i];

        copyIndexes[0] = 0;
        std::sort(copyIndexes, copyIndexes + count + 1);

        // 在对索引堆中的索引进行排序后, 应该正好是1...count这count个索引
        bool res = true;
        for( int i = 1 ; i <= count ; i ++ )
            if( copyIndexes[i-1] + 1 != copyIndexes[i] ){
                res = false;
                break;
            }

        delete[] copyIndexes;

        if( !res ){
            cout<<"Error!"<<endl;
            return false;
        }

        return true;
    }
    void printfData(){
        for (int i = 1; i <=count; ++i)
            cout<<data[i]<<"\t";
            cout<<endl;
    }
    void printfIndexes(){
        for (int i = 1; i <=count; ++i)
            cout<<indexes[i]<<"\t";
            cout<<endl;
    }
    void printfDataByIndexes(){
        for (int i = 1; i <=count; ++i)
            cout<<data[indexes[i]]<<"\t";
        cout<<endl;
    }
};
template<typename T>
void heapSortUsingIndexMaxHeap(T arr[], int n){

    IndexMaxHeap<T> indexMaxHeap = IndexMaxHeap<T>(n);
    for( int i = 0 ; i < n ; i ++ )
        indexMaxHeap.insert( i , arr[i] );
    for (int j = 0; j <n; ++j) cout<<j+1<<"\t";
    cout<<endl;
    indexMaxHeap.printfData();
    indexMaxHeap.printfIndexes();
    indexMaxHeap.printfDataByIndexes();
    assert( indexMaxHeap.testIndexes() );

//    for( int i = n-1 ; i >= 0 ; i -- )
//        arr[i] = indexMaxHeap.extractMax();
}

int main() {

//    int n = 1000000;
//
//    int* arr = SortTestHelper::generateRandomArray(n, 0, n);
//    SortTestHelper::testSort("Heap Sort Using Index-Max-Heap", heapSortUsingIndexMaxHeap, arr, n);
//    delete[] arr;
    int n=10;
    int arr[n]={33,55,16,86,14,17,28,51,48,21};
    heapSortUsingIndexMaxHeap(arr,n);
    return 0;
}

